package com.cat.DataStructure04;

import java.util.Arrays;

/**
*   @description https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/
*   @author 曲大人的喵
*   @create 2025/11/25 19:12
*   @since JDK17
*/

class Solution11 {
    public int longestPalindrome(String word1, String word2) {
        char[] s = (word1 + word2).toCharArray();
        int n = s.length, ans = 0;
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    if (i < word1.length() && j >= word1.length()) {
                        ans = Math.max(ans, f[i][j]);
                    }
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return ans;
    }
}
